package java111_2;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class Day29 {
    //https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        int count = 0;
        int i = 0;
        while(i < n){
            if(i == n-1){
                count++;
                break;
            }
            if(arr[i] < arr[i+1]) {
                while (i + 1 < n && arr[i] <= arr[i + 1]) {
                    i++;
                }
                count++;
            } else if (arr[i] > arr[i+1]) {
                while (i + 1 < n && arr[i] >= arr[i + 1]) {
                    i++;
                }
                count++;
            } else {
                while (i + 1 < n && arr[i] == arr[i + 1]) {
                    i++;
                }
            }
            i++;
        }
        System.out.println(count);
    }

    //https://ac.nowcoder.com/acm/problem/219038
    public static void main2(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while(n-- > 0){ // 贪心加数学
            int x = in.nextInt() - 1;
            int res = 1, tmp = 1;
            while(x != 0){
                if(x % (2 * tmp) == 0){
                    x -= 2 * tmp;
                    tmp *= 2;
                } else {
                    x -= tmp;
                }
                res++;
            }
            System.out.println(res);
        }
    }

    //https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237?tpId=196&tqId=39285&ru=/exam/oj
    public static void main3(String[] args) {
        Day29 d = new Day29();
        System.out.println(d.LIS(new int[]{1, 4, 7, 5, 6}));

    }
    public int LIS (int[] a) {
        // 贪心 + 二分
        // list 中存储长度为 x 的子序列的末尾的数字
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < a.length; i++){
            int left = 0, right = list.size();
            while(left < right){
                int mid = (left + right) / 2;
                if(a[i] < list.get(mid)){
                    right = mid;
                } else {
                    left = mid+1;
                }
            }
            if(left >= list.size()) {
                list.add(a[i]);
            } else {
                list.set(left, a[i]);
            }
        }
        return list.size();
    }

    public static void main(String[] args) {
        // 速度 foreach <= for
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(10000);
        }
        long sum = 0;
        long start = System.currentTimeMillis();
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start + " " + sum);
        sum = 0;

        start = System.currentTimeMillis();
        for (int tmp: arr) {
            sum += tmp;
        }
        end = System.currentTimeMillis();
        System.out.println(end - start + " " + sum);
    }
}
